1. Field of the Invention
This invention generally relates to an efficient coding system and more particularly to a highly efficient coding system which can perform highly efficient coding of a small block of an input image.
2. Description of the Related Art
Half tone image signals, of which a typical example is television signals, include a vast quantity of information. Therefore, a broad-band transmission line is necessary for transmission of such half tone image signals. Further, a bulk memory is necessary for recording of such half tone image signals.
On the other hand, redundancy, that is, self-correlation of such an image signal is high. Thus, efficient coding systems and methods for reducing the redundancy of the image signal and for efficiently transmitting and recording the image have been studied and developed.
Typical and fundamental methods for reducing the redundancy are a predictive coding and a transform coding and so on.
First, the predictive coding, which is referred to also as a differential coding or a differential pulse-code modulation (PCM), is a method which predicts the current sampled value of a pixel or picture element from the actual sampled value of a pixel already coded and then effects coding of a prediction error, that is, a difference between the predicted value and the actual value.
Further, the transform coding is a method wherein first, sampled values of data indicated by original image signals are transformed as to "bases" which are independent of or intersect orthogonally to each other, that is, effect an orthogonal transform of each block of original image data represented by original signals to obtain components, which are adapted to characteristics of the original image data and are independent with each other, and then coding of the components is effected.
Hereinafter, the transform coding will be described in detail.
First, it is to be noted that generally, low-frequency components of image signals have a large proportion of electric power of the image signals and thus high-frequency components of image signals have a small portion of the electric power thereof but the latter components play an important role in representing information.
Therefore, the coding of the original image signals can be efficiently performed as a whole by first transforming the image signals into such components, then effecting quantization of each of such components in a manner suitably adapted thereto, further coding the result of the quantization, thereafter transmitting the resultant codes to a receiving system and finally performing an inverse transform of the transmitted codes in the receiving system to restore the original image.
Thus, in the transform coding, an original image or picture is first divided into blocks each composed of a suitable number of pixels. Then, as to each of the blocks, an orthogonal transform of a sequence of sampled numerical values is effected. That is, a linear transformation of the sequence of the sampled values is performed with respect to "bases" which are adapted to characteristics of the original image signals and are independent of each other.
Thus, the resultant components (that is, the values obtained by the transformation) become more independent of, that is, more uncorrelated to each other in comparison with the original sampled values. Thereby, redundant information can be reduced.
In short, the predictive coding is a method to reduce the correlation among the sampled data by performing a transforming operation on a "time domain" and on the other hand the transform coding is a method to eliminate the correlation by a transforming operation on a "frequency domain".
As a result, the electric power is distributed to specific components, that is, to a limited range of components of the image signals due to statistical properties of the image signals. Then, further taking visual characteristics of the restored image into consideration, a greater number of bits are allocated to the components of which electric power is large, and in contrast the components, of which electric power is small, are coarsely quantized by use of a small number of bits. Thereby, a bit rate, that is, a number of bits per block can be reduced as a whole.
Generally, Fourier transform is familiar to an orthogonal transformation. However, in the technical field of image signal processing, Discrete Cosine Transform (DCT) is mainly used.
Further, the order of the transform is usually set as, for example, 4, 8 or 16. In general, the higher the order of the transform becomes, the higher the efficiency of the coding becomes.
Incidentally, a large quantity of literature is available on the transform coding. For example, in an article entitled "Discrete Cosine Transform" by N. Ahmed, T. Natarajan and K. R. Rao, IEEE Transactions on Computers, January 1974, a discrete cosine transform (DCT) is defined and an algorithm to compute it using the fast Fourier transform is developed. It is shown that the discrete cosine transform can be used in the area of digital processing for the purposes of pattern recognition and Wiener filtering. Its performance is compared with that of a class of orthogonal transforms and is found to compare closely to that of the Karhunen-Loeve transform, which is known to be optimal. The performance of the Karhunen-Loeve and discrete cosine transforms are also found to compare closely with respect to the rate-distortion criterion.
The DCT of a data sequence X(m), m=0, 1, . . . , (M-1) is defined as ##EQU1## where G.sub.x (k) is the kth DCT coefficient. It is worthwhile noting that the set of basis vectors {1/.sqroot.2, cos ((2 m+1)k.pi.)/(2M)} is actually a class of discrete Chebyshev polynomials. This can be seen by recalling that Chebyshev polynomials can be defined as (3) ##EQU2## where T.sub.k (.xi..sub.p) is the kth Chebyshev polynomial.
Now, in (2), .xi..sub.p is chosen to be the pth zero of T.sub.M (.xi.), which is given by (3) ##EQU3## Substituting (3) in (2), one obtains the set of Chebyshev polynomials ##EQU4## From (4) it follows that the T.sub.k (p) can equivalently be defined as ##EQU5## Comparing (5) with (1) we conclude that the basis member cos ((2 m+1)k.pi.)/(2M) is the kth Chebyshev polynomial T.sub.k (.xi.) evaluated at the mth zero of T.sub.M (.xi.).
Again, the inverse cosine discrete transform (ICDT) is defined as ##EQU6## We note that applying the orthogonal property (3) ##EQU7## to (6) yields the DCT in (1).
If (6) is written in matrix form and .LAMBDA. is the (M.times.M) matrix that denotes the cosine transformation, then the orthogonal property can be expressed as ##EQU8## where .LAMBDA..sup.T is the transpose of .LAMBDA. and [I] is the (M.times.M) identity matrix.
Thus, the foregoing has shown that the DCT can be used in the area of image processing for the purposes of feature selection in pattern recognition; and scalar-type Wiener filtering. Its performance compares closely with that of the LKT, which is considered to be optimal. The performances of the KLT and DCT are also found to compare closely, with respect to the rate-distortion criterion.
However, the conventional transform coding has the following problem. Indeed, when the order of the transform is increased, the numerical efficiency of the coding becomes higher but subjective picture quality, that is, picture quality obtained by actual visual evaluation of a restored picture is not always improved.
The causes of this are as follows. First, as the order of the transform increases, the shape of a block distortion becomes a large block-like one to an extent sufficient to be conspicuous in the restored picture. Further, errors occur in a wide range from peripheral portions of edges of an object to a flat portion in which the gray level is not substantially changed and thus picture quality is often degraded.
Further, by the orthogonal transform, fine figures or patterns such as a thin segment are decomposed into components thereof in such a manner to disappear from a picture. Thus, in this respect, the picture quality is degraded.
Moreover, in a case where the order of the transform is high, unless the precision of computation in a coding system is equal to that of computation in the decoding (receiving) system, the picture quality is degraded. Therefore, in such a case, it is necessary for improving the picture quality to make the precision of computation high in both the coding system and the receiving system.
In order to make the precision of computation high, there is a necessity for increasing word length employed in processing in hardware. Thus, the conventional transform coding has another problem that the size of the hardware becomes large and the cost is increased.
The higher the order of the transform becomes, the more conspicuous the drawbacks have become.
The present invention is provided to eliminate the defects of the conventional coding system.
It is therefore an object of the present invention to provide an highly efficient coding system which can very efficiently perform coding with a relatively low order of the orthogonal transform, a simple configuration and a low cost and without the degradation of the subjective picture quality as caused in the conventional system by effecting normalization at least two times, that is, performing interblock normalization and normalization of data in each block.